package com.zhaofan.other;

//给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,3,3,4,4,5]
//输出：[1,2,5]
//
//
// 示例 2：
//
//
//输入：head = [1,1,1,2,3]
//输出：[2,3]
//
//
//
//
// 提示：
//
//
// 链表中节点数目在范围 [0, 300] 内
// -100 <= Node.val <= 100
// 题目数据保证链表已经按升序 排列


import org.junit.Test;

public class No82 {

    @Test
    public void test(){
        int[] arr={1,2,3,3,4,4,5};
        ListNode headNode=new ListNode(),curNode=headNode;
        for (int i : arr) {
            curNode.next=new ListNode(i);
            curNode=curNode.next;
        }
        ListNode listNode = deleteDuplicates(headNode.next);
        print(listNode);
    }

    private void print(ListNode listNode) {
        if(listNode==null) return;
        System.out.println(listNode.val);
        print(listNode.next);
    }

    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null) return head;
        head=new ListNode(Integer.MIN_VALUE,head);
        ListNode curNode=head.next,lastNode=head;
        while (curNode!=null) {
            if(curNode.next!=null&&curNode.val==curNode.next.val){//说明curNode和下一个元素重复，找到重复的所有元素
                ListNode dNode=curNode;
                while(dNode!=null){
                    if(dNode.val== dNode.next.val){
                        if(dNode.next.next==null){
                            curNode=null;
                            lastNode.next=null;
                            break;
                        }
                        dNode=dNode.next;
                    }else{
                        //lastNode.next=dNode.next;//将不重复的元素加
                        //lastNode=lastNode.next;
                        curNode=dNode.next;
                        break;
                    }
                }
            }else {
                lastNode.next=curNode;
                lastNode=lastNode.next;
                curNode=curNode.next;
            }
        }
        return head.next;
    }

    public ListNode deleteDuplicates1(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        while(cur.next!=null&&cur.next.next!=null){
            if(cur.next.val==cur.next.next.val){
                int x=cur.next.val;
                while (cur.next!=null&&cur.next.val==x){
                    cur.next=cur.next.next;
                }
            }else {
                cur=cur.next;
            }
        }
        return dummy.next;
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }
}



